package practice1_100;

public class Practice115 {
    public int numDistinct(String s, String t) {
        //动态规划，将t拆成若干子字符串
        //新建立dp数组
        int[][] dp =new int[s.length()][t.length()];

//        for (int i = 0; i < ; i++) {
//
//        }


        char[] tArr = t.toCharArray();
        int a = dp(s, t, 0, 0);
        return a;
    }

    private int dp(String s, String t, int sInd, int tInd) {
        int res = 0;
        if (sInd >= s.length() || tInd >= t.length()) return 0;
        if (sInd < s.length() && tInd == t.length() - 1 && t.charAt(tInd) == s.charAt(sInd)) return 1;
        int a=0,b=0;
        if (s.charAt(sInd) == t.charAt(tInd)) {
             a = dp(s, t, sInd+1, tInd + 1)+dp(s,t,sInd+1,tInd);
        }else {
            b=dp(s,t,sInd+1,tInd);
        }
        res=a+b;
        return res;
    }

    public static void main(String[] args) {
        int res =new Practice115().numDistinct("baa","ba");
        System.out.println(res);
    }
}
